package 其他.demo_01背包问题;

/**
 * 物品 下标: 0 1 2
 * 重量:     1 3 4
 * 价值:     15 20 30
 * 背包容量为: 0 1 2 3 4
 *
 */
public class Main {
    public static void main(String[] args) {
        int[][] dp = new int[3][5];
        int[] weight={1,3,4};
        int[] value={15,20,30};
        int bagWeight=4;
        //1.初始化部分数组元素
        // 横向
        for (int j = 0; j < weight[0]; j++) {
            dp[0][j]=0;
        }
        for (int j = weight[0]; j <=bagWeight ; j++) {
            dp[0][j]=value[0];
        }
        // 纵向
        for (int i = 0; i < weight.length; i++) {
            dp[i][0]=0;
        }

        //2.开始遍历, 外层遍历 物品 , 内层遍历 背包
        for (int i = 1; i < weight.length; i++) {
            for (int j = 0; j <= bagWeight; j++) {
                if (j<weight[i]){
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                }
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }

    }
}
